package com.example.leetdemo.finash;

public class Solution689 {
    public static void main(String[] args) {
        Solution689 solution689 = new Solution689();
        int[] result = solution689.maxResult2(new int[] {7,13,20,19,19,2,10,1,1,19},  3);
        for (int i = 0; i < 3; i++) {
            System.err.println(result[i]);
        }
    }

    /**
     * 暴力 超时
     * @param nums
     * @param k
     * @return
     */
    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        int[] arr = new int[3];
        int[][] dp = new int[nums.length - 3 * k + 1][2];
        int[] test = new int[nums.length - k + 1];
        for (int i =0; i <= nums.length - k; i++) {
            test[i] = sum(nums, k, i);
//            System.err.print(test[i] + " ");
        }
//        System.err.println();
        for (int i = 0; i <= nums.length - 3 * k; i++) {
            for (int j = i + k; j <= nums.length - 2 * k; j++) {
                for (int n = j + k; n <= nums.length - k; n++) {
                    if (dp[i][1] == 0 || dp[i][0] ==0) {
                        dp[i][1] = n;
                        dp[i][0] = j;
                    }
                    if (test[dp[i][1]] + test[dp[i][0]] < test[n] + test[j]) {
                        dp[i][1] = n;
                        dp[i][0] = j;
                    }
                }
            }
        }
        int result = 0;
        int index = 0;
        for (int i = 0; i<= nums.length - 3 * k; i++) {
//            System.err.println(i + " " + dp[i][0] + " " + dp[i][1]);
            if (test[i] + test[dp[i][0]] + test[dp[i][1]] > result && dp[i][0] !=0 && dp[i][1] != 0) {
                result = test[i] + test[dp[i][0]] + test[dp[i][1]];
                index = i;
            }
        }
        arr[0] = index; arr[1] = dp[index][0]; arr[2] = dp[index][1];
        return arr;
    }

    private int sum(int[] num, int k, int i) {
        int sum = 0;
        for (int j = 0; j < k; j++) {
            sum += num[i + j];
        }
        return sum;
    }

    /**
     * 第二次还是超时
     * @param nums
     * @param k
     * @return
     */
    private int[] maxResult(int[] nums, int k) {
        int[] arr = new int[3];
        int[][] dp = new int[nums.length - 3 * k + 1][3];
        int[] test = new int[nums.length - k + 1];
        for (int i =0; i <= nums.length - k; i++) {
            test[i] = sum(nums, k, i);
//            System.err.print(test[i] + " ");
        }
//        System.err.println();
        for (int i = 0; i <= nums.length - 3 * k; i++) {
            if (i > 0) {
                dp[i][0] = i;
                if (i < dp[i - 1][1] - k && test[i] > test[dp[i][0]]) {
                    dp[i][1] = dp[i - 1][1];
                    dp[i][2] = dp[i - 1][2];
                } else {
                    for (int j = i + k; j <= nums.length - 2 * k; j++) {
                        dp[i][1] = j;
                        if (j < dp[i - 1][2] - k && test[j] > test[dp[i][1]]) {
                            dp[i][2] = dp[i - 1][2];
                        } else {
                            for (int n = j + k; n <= nums.length - k; n++) {
                                if (dp[i][1] == 0 || dp[i][2] == 0) {
                                    dp[i][2] = n;
                                    dp[i][1] = j;
                                }
                                if (test[dp[i][1]] + test[dp[i][2]] < test[n] + test[j]) {
                                    dp[i][2] = n;
                                    dp[i][1] = j;
                                }
                            }
                        }
                    }
                }
            }
            for (int j = i + k; j <= nums.length - 2 * k; j++) {
                for (int n = j + k; n <= nums.length - k; n++) {
                    if (dp[i][2] == 0 || dp[i][1] ==0) {
                        dp[i][2] = n;
                        dp[i][1] = j;
                    }
                    if (test[dp[i][1]] + test[dp[i][2]] < test[n] + test[j]) {
                        dp[i][2] = n;
                        dp[i][1] = j;
                    }
                }
            }
        }
        int result = 0;
        int index = 0;
        for (int i = 0; i<= nums.length - 3 * k; i++) {
//            System.err.println(i + " " + dp[i][0] + " " + dp[i][1]);
            if (test[dp[i][2]] + test[dp[i][0]] + test[dp[i][1]] > result) {
                result = test[dp[i][0]] + test[dp[i][1]] + test[dp[i][2]];
                index = i;
            }
        }
        arr[0] = dp[index][0]; arr[1] = dp[index][1]; arr[2] = dp[index][2];
        return arr;
    }


    /**
     * 过了
     * 第三次
     */
    private int[] maxResult2(int[] nums, int k) {
        int[] arr = new int[3];
        int[][] dp = new int[nums.length][2];
        int[] test = new int[nums.length - k + 1];
        for (int i =0; i <= nums.length - k; i++) {
            test[i] = sum(nums, k, i);
//            System.err.print(test[i] + " ");
        }

        for (int j = k; j <= nums.length - 2 * k; j++) {
            for (int n = j + k; n <= nums.length - k; n++) {
                if (dp[j][1] == 0 || dp[j][0] ==0) {
                    dp[j][0] = j;
                    dp[j][1] = n;
                }
                if (test[dp[j][1]] + test[dp[j][0]] < test[n] + test[j]) {
                    dp[j][0] = j;
                    dp[j][1] = n;
                }
            }
        }
        int sum = 0;
        for (int i = 0; i <= nums.length - 3 * k; i++ ) {
            for (int j = i + k; j < dp.length ; j++) {
                if (dp[j][0] == 0 || dp[j][1] ==0) {
                    continue;
                }
                int var = test[i] + test[dp[j][0]] + test[dp[j][1]];
                if (var > sum) {
                    sum = var;
                    arr[0] = i; arr[1] = dp[j][0]; arr[2] = dp[j][1];
                }
            }
        }

        return arr;
    }


    private int[] max4(int[] nums, int k) {
        int[] arr = new int[3];
        int[][] dp = new int[nums.length][2];
        int[] sumList = new int[nums.length - k + 1];
        for (int i =0; i <= nums.length - k; i++) {
            sumList[i] = sum(nums, k, i);
        }

        for (int j = k; j <= nums.length - 2 * k; j++) {
            for (int n = j + k; n <= nums.length - k; n++) {
                if (dp[j][1] == 0 || dp[j][0] ==0) {
                    dp[j][0] = j;
                    dp[j][1] = n;
                }
                if (sumList[dp[j][1]] + sumList[dp[j][0]] < sumList[n] + sumList[j]) {
                    dp[j][0] = j;
                    dp[j][1] = n;
                }
            }
        }
        int sum = 0;
        for (int i = 0; i <= nums.length - 3 * k; i++ ) {
            for (int j = i + k; j < dp.length ; j++) {
                if (dp[j][0] == 0 || dp[j][1] ==0) {
                    continue;
                }
                int var = sumList[i] + sumList[dp[j][0]] + sumList[dp[j][1]];
                if (var > sum) {
                    sum = var;
                    arr[0] = i; arr[1] = dp[j][0]; arr[2] = dp[j][1];
                }
            }
        }

        return arr;
    }
}
